//
// Created by 紫霄 on 2020/3/30.
//

#ifndef CPP_DEMO_BINTREEDEMO_H
#define CPP_DEMO_BINTREEDEMO_H

#include <queue>
#include <stack>
#include <sys/attr.h>

#define BinNodePos(T) BinNode<T> *
#define nodeHeight(x) ((x) ? (x->height) : -1) //// -1太巧妙了

using namespace std;
//// 节点类
template <typename T> struct BinNode {
  BinNodePos(T) Parent, Lchild, Rchild;
  T data;
  int size();
  int height;
  BinNodePos(T) insertAsL(T const &data);
  BinNodePos(T) insertAsR(T const &data);
  template <typename VST> void travPre_v1(VST &visit);
  template <typename VST> void travPre_v2(VST &visit);
  template <typename VST> void travCen(VST &visit);
  template <typename VST> void travLevel(VST &visit);
  template <typename VST> void travAfter(VST &visit);
};

//// 二叉树类
template <typename T> class BinTree {
protected:
  int _size;
  BinNodePos(T) _root;
  virtual int updateNodeHeight(BinNodePos(T) x);
  void updateNodeHeightAbove(BinNodePos(T) x);

public:
  int size() const { return _size; }
  bool empty() const { return !_root; }
  BinNodePos(T) root() const { return _root; }
  BinNodePos(T) insertAsL(T const &, BinNodePos(T));
  BinNodePos(T) insertAsR(T const &, BinNodePos(T));
};

//// 节点内函数定义
template <typename T> BinNodePos(T) BinNode<T>::insertAsL(T const &e) {
  return Lchild = new BinNode<T>(e, this); // TODO: 如何实现的
}
template <typename T> BinNodePos(T) BinNode<T>::insertAsR(T const &e) {
  return Rchild = new BinNode<T>(e, this);
}
template <typename T> int BinNode<T>::size() {
  int size = 1;
  if (Lchild)
    size += Lchild.size();
  if (Rchild)
    size += Rchild.size();
  return size;
}

// travPre v1 版本；
template <typename T>
template <typename VST>
void BinNode<T>::travPre_v1(VST &visit) {
  stack<BinNodePos(T)> s;
  s.push(this);
  while (!s.empty()) {
    BinNodePos(T) k = s.top();
    visit(k->data);
    s.pop();
    if (k->Rchild) { //右边先进入后出
      s.push(k->Rchild);
    }
    if (k->Lchild) { //左边后进先出
      s.push(k->Lchild);
    }
  }
}
// travPre V2 版本；
template <typename T>
template <typename VST>
void BinNode<T>::travPre_v2(VST &visit) {
  stack<BinNodePos(T)> S;
  BinNodePos(T) x = this;
  while (true) {
    visitAlongLiftBranch(x, visit, S);
    if (S.empty())
      break;
    S.pop();
  }
}

template <typename VST, typename T>
static void visitAlongLiftBranch(BinNodePos(T) x, VST &visit,
                                 stack<BinNode<T> *> &S) {
  while (x) {
    visit(x->data);
    S.push(x->Rchild);
    x = x->Lchild;
  }
}
// 中序遍历
template <typename VST, typename T>
static void goAlongLiftBranch(BinNodePos(T) x, VST &visit,
                              stack<BinNode<T> *> &S) {
  while (x) {
    S.push(x);
    x = x->Lchild;
  }
}

// 中序遍历 主函数
template <typename T>
template <typename VST>
void BinNode<T>::travCen(VST &visit) {
  stack<BinNodePos(T)> S;
  BinNodePos(T) x = this;
  while (true) {
    goAlongLiftBranch(x, visit, S);
    if (S.empty())
      break;
    x = S.top();
    S.pop();
    visit(x->data);
    x = x->Rchild;
  }
}

// 更新了层次访问
template <typename T>
template <typename VST>
void BinNode<T>::travLevel(VST &visit) {
  queue<BinNodePos(T)> Q;
  Q.push(this);
  while (!Q.empty()) {
    BinNodePos(T) x = Q.front();
    visit(x->data);
    if (x->Lchild)
      Q.push(x->Lchild);
    if (x->Rchild)
      Q.push(x->Rchild);
  }
}

// 更新了后序遍历
template <typename T> void findLeaf(stack<BinNodePos(T)> &S) {
  BinNodePos(T) x = S.top();
  while (x) {
    if (x->Lchild) {
      if (x->Rchild) { //假如还有右孩子，右孩子先进后出
        S.push(x->Rchild);
      }
      S.push(x->Lchild);

    } else { //实在不行就转去右孩子
      S.push(x->Rchild);
    }
    x = S.top(); // 注意这里不是x = x->Lchild;
                 // 假如某个节点没有左孩，有右孩子，且右孩子又存在孩子
  }
  S.pop(); // 跳出循环的条件是空，意味着到达了叶子，叶子的右节点是空，这里弹出空节点
}

template <typename T>
template <typename VST>
void BinNode<T>::travAfter(VST &visit) {
  stack<BinNode(T)> S;
  BinNodePos(T) x = this;
  S.push(x);
  while (!S.empty()) {
    if (S.top() != x->Parent) { // 假如S的顶元素不是上次访问节点的父节点，
      // 那么肯定是右节点，这里对右节点子树同样做找最左边叶子的遍历
      findLeaf(S);
    } // else do nothing
    x = S.top();
    S.pop();
    visit(x->data);
  }
}

#endif // CPP_DEMO_BINTREEDEMO_H
